package arithmetic;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

/**
 * 用最小的索引和，寻找两个人共同喜欢的餐厅
 *
 * @author Gaojie
 * @date 2022/3/14 19:35
 */
public class FindRestaurant {

    @Test
    void test() {

        String[] list1 = new String[]{"B"};
        String[] list2 = new String[]{"A", "B"};
        assert Arrays.equals(fun(list1, list2), new String[]{"B"});

        list1 = new String[]{"Shogun", "Tapioca Express", "Burger King", "KFC"};
        list2 = new String[]{"Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"};
        assert Arrays.equals(fun(list1, list2), new String[]{"Shogun"});

        list1 = new String[]{"A", "B", "C", "D"};
        list2 = new String[]{"D", "C", "B", "A"};
        assert Arrays.equals(fun(list1, list2), new String[]{"A", "B", "C", "D"});
    }

    /**
     * 1.定义最小索引
     * 2.两次 for 循环，找出最小索引，并记录对应坐标在 map
     * 3.从 map 找出对应最小索引的下标，将其值存入 list
     * 4. list 转成数组
     */
    String[] fun(String[] list1, String[] list2) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int l1 = list1.length, l2 = list2.length, minIndex = l1 + l2 - 1;
        for (int i = 0; i < l1 && i <= minIndex; i++) {
            for (int j = 0; j < l2 && j <= minIndex - i; j++) {
                if (list1[i].equals(list2[j])) {
                    int index = i + j;
                    if (index <= minIndex) {
                        minIndex = index;
                        map.put(i, j);
                        break;
                    }
                }
            }
            System.out.printf("map: %s%n", map);
        }
        System.out.printf("minIndex: %d%n", minIndex);

        // 从map中找出符合条件的
        ArrayList<String> names = new ArrayList<>();
        for (Integer k : map.keySet()) {
            Integer v = map.get(k);
            if (k + v == minIndex) {
                names.add(list1[k]);
                System.out.printf("k: %d, v: %d, name: %s%n", k, v, list1[k]);
            }
        }
        System.err.println(names);
        return names.toArray(new String[]{});
    }
}
